UVa/11463 - Commandos/11463.cpp

   1 #include <iostream>
   2 #include <algorithm>
   3
   4 using namespace std;
   5
   6 const int MAXN = 100;
   7
   8 unsigned int g[MAXN][MAXN];
   9
  10 int main(){
  11   int T;
  12   cin >> T;
  13   for (int C=1; C <= T; C++){
  14     int n;
  15     cin >> n;
  16
  17     for (int i=0; i<n; ++i){
  18       for (int j=0; j<n; ++j){
  19         g[i][j] = INT_MAX;
  20       }
  21       g[i][i] = 0;
  22     }
  23
  24     int R;
  25     cin >> R;
  26     while (R--){
  27       int i, j;
  28       cin >> i >> j;
  29       g[i][j] = g[j][i] = 1;
  30     }
  31     int start, end;
  32     cin >> start >> end;
  33
  34     for (int k=0; k<n; ++k){
  35       for (int i=0; i<n; ++i){
  36         for (int j=0; j<n; ++j){
  37           g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
  38         }
  39       }
  40     }
  41
  42     unsigned int answer = 0;
  43     for (int i=0; i<n; ++i){
  44       answer = max(answer, g[start][i] + g[i][end]);
  45     }
  46
  47     cout << "Case " << C << ": " << answer << endl;
  48   }
  49   return 0;
  50 }